package com.mango.leet.code.middle;

/**
 * 面试题 01.05. 一次编辑
 * @Author: mango
 * @Date: 2022/5/13 11:56 下午
 */

/**
 * 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
 *
 *  
 *
 * 示例 1:
 *
 * 输入:
 * first = "pale"
 * second = "ple"
 * 输出: True
 *  
 *
 * 示例 2:
 *
 * 输入:
 * first = "pales"
 * second = "pal"
 * 输出: False
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/one-away-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC0105 {
    public static void main(String[] args) {
        String first = "teacher";
        String second = "teather";
        System.out.println(new Solution().oneEditAway(first,second));
    }
    static class Solution {
        // 双指针
        public boolean oneEditAway(String first, String second) {
            int n1 = first.length();
            int n2 = second.length();
            // 如果2个字符长度相差>1，则直接返回false
            if(Math.abs(n1 - n2) > 1){
                return false;
            }
            // 如果2个字符长度相等且=1，直接返回true
            if(n1 == n2 && n1==1){
                return true;
            }
            int l1 = 0;
            int l2 = 0;
            int r1 = n1 - 1;
            int r2 = n2 - 1;
            int editCount = 0;
            while (l1 <= r1 && l2 <= r2){
                if(first.charAt(l1) != second.charAt(l2) && editCount < 2){
                    editCount++;
                    if(n1 > n2){
                        l1++;
                    }else if(n1 == n2){
                        l1++;
                        l2++;
                    }else{
                        l2++;
                    }
                }else {
                    l1++;
                    l2++;
                }
                if(l1 <= r1 && l2 <= r2 && first.charAt(r1) != second.charAt(r2) && editCount < 2){
                    editCount++;
                    if(n1 > n2){
                        r1--;
                    }else if(n1 == n2){
                        r1--;
                        r2--;
                    }else{
                        r2--;
                    }
                }else {
                    r1--;
                    r2--;
                }
                if(editCount > 1){
                    break;
                }
            }
            return editCount < 2;
        }
    }
}
